//=====================================================================
//
//    NOTE: all of these algorithms are based off the 'scope tree'
//          concept. that is, when going up [sic], they will go up
//          the tree until they reach the root.
//
//=====================================================================
#ifndef KALEIDOSCOPE_SCOPE_ALGORITHM_HPP
#define KALEIDOSCOPE_SCOPE_ALGORITHM_HPP
//=====================================================================
#include <sooty/frontend/syntactic_analysis/parseme.hpp>
#include <kaleidoscope/kaleidoscope.hpp>
//=====================================================================
KALEIDOSCOPE_BEGIN
//=====================================================================
	
	//=====================================================================
	// upwards_scope_leveller:
	// because there are some instances where checking all the children of 
	// a 'level' in the tree is silly (ie, return-statement, etc), this 
	// function will go up to the next sensible 'level'
	//=====================================================================
	namespace scope {
		namespace detail {
			atma::sooty::parseme_ptr upwards_scope_leveller(atma::sooty::parseme_ptr_ref);
		}
	}
	
	//=====================================================================
	// upwards_copy_if:
	//=====================================================================
	namespace scope
	{
		template <typename IT, typename PR>
		void upwards_copy_if(atma::sooty::const_parseme_ptr_ref starting_node, IT dest, PR pred)
		{
			parseme_ptr current_node = starting_node;
			for (;;) {
				if (current_node->id == ids::root) break;
				current_node = detail::upwards_scope_leveller(current_node);
				parseme_container& children = current_node->children;

				for (parseme_container::const_iterator i = children.begin(); i != children.end(); ++i)
					if (pred(*i))
						*dest++ = *i;
			}
		}
	}
	
	//=====================================================================
	// upwards_for_each:
	//=====================================================================
	namespace scope
	{
		template <typename FN>
		void upwards_for_each(atma::sooty::const_parseme_ptr_ref starting_node, FN func)
		{
			parseme_ptr current_node = starting_node;
			for (;;) {
				if (current_node->id == ids::root) break;
				current_node = detail::upwards_scope_leveller(current_node);
				parseme_container& children = current_node->children;

				for (parseme_container::const_iterator i = children.begin(); i != children.end(); ++i)
					func(*i);
			} 
		}
	}
	
	//=====================================================================
	// upwards_find_first_of: if not found, returns a null pointer
	//=====================================================================
	namespace scope
	{
		template <typename PR>
		atma::sooty::parseme_ptr upwards_find_first_if(atma::sooty::const_parseme_ptr_ref starting_node, PR pred)
		{
			parseme_ptr current_node = starting_node;
			for (;;) {
				if (current_node->id == ids::root) break;
				current_node = detail::upwards_scope_leveller(current_node);
				parseme_container& children = current_node->children;

				for (parseme_container::const_iterator i = children.begin(); i != children.end(); ++i)
					if (pred(*i))
						return *i;
			} 
			
			return parseme_ptr();
		}
	}
	
//=====================================================================
KALEIDOSCOPE_CLOSE
//=====================================================================
#endif
//=====================================================================

